package com.leetcode;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No74
 * @description 74. 搜索二维矩阵
 * @date 2021/1/27 下午2:39
 */
public class No74 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        int target = 23;
        System.out.println(searchMatrix(matrix,target));
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
            return false;
        }
        int rows = matrix.length, cols = matrix[0].length;
        int left = 0, right = rows * cols - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            //关键 定位元素
            int element = matrix[mid / cols][mid % cols];
            if (element == target) {
                return true;
            } else if (element < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

}
